Telecommunications networks use buffer memories or queues for a wide variety of purposes. In this specification, buffer memories, buffers, queues and FIFOs are used synonymously, as are cells and packets of data. A telecommunications node such as, a switching element, router, multiplexer e.g., statistical multiplexer, receives data packets at a plurality of input ports and transports them to one or more of its appropriate output ports. Queues are often used at the input and output ports to store the packets temporarily while the node processes the packet headers and executes appropriate actions. The queues are also used to regulate the flow of packets between two nodes or between two stages of modules which make up a node or nodes. The movement of data packets between the stages or nodes is regulated by using available queue space upstream of the congested stage to store data packets intended for it. The queues must, however, be managed properly so that they do not overflow or underflow. For example, when a queue receives packets faster than it can dispose of them, the packets build up in the queue, resulting in a phenomenon called a queue overflow. On the other hand, when it receives packets slower than it is capable of draining, a starved queue or a queue underflow results. In either situation, the performance of the network suffers.
A flow control mechanism between two stages is therefore needed to prevent overflow or underflow of queues. In one example of flow control schemes, a single flow control signal is a binary variable which is transmitted periodically from the second stage (downstream) device to the first stage (upstream) device. The flow control signal takes one of two values: Go; or Stop. A value of Go indicates that the first stage device is permitted to send to the second stage device queue, whereas a value of Stop indicates that the first stage device is not permitted to send to the second stage device queue. The binary flow control such as that described above is typically referred to as backpressure control scheme. The syntax of the flow control signal is typically specified under standard to permit the interoperability of devices.
A single flow control signal exists for each queue in the second stage device. The second stage asserts an independent flow control signal for each queue. The first stage is able to independently schedule traffic destined to each second stage queue so as to avoid head of line blocking. A transmission path of packets is usually made up of many stages and nodes, and the process can be carried back all the way to the first stage in the transmission path.
U.S. Pat. No. 5,673,254 Sep. 30, 1997 Crayford, U.S. Pat. No. 5,787,071 Jul. 28, 1998 Basso et al, U.S. Pat. No. 5,475,682 Dec. 12, 1995 Choudhury et al, U.S. Pat. No. 5,453,980 Sep. 26, 1995 Van Engelshoven describe several variations of backpressure schemes.
FIG. 1 shows a very simple functional block illustration of a switch 10. For example, there are multiple input linecards 12, a switch fabric 14 and multiple output linecards 16. The switch also includes a processor 18 for coordinating the operations of linecards and switch fabric. At 20, data packets come in to an input port of a linecard from e.g., an optical cable, the linecard performs some work and sends the packets through the fabric to another linecard, which in turn transports the packets through its output port at 22 after performing appropriate actions. In a linecard, there may be multiple devices 24 and a separate processor 26 for a variety of functions. Data flows through the multiple devices. When data moves from one device to the next or from one linecard to another through a switch fabric through a connection such as a link or a bus, one device must tell the other to slow down or keep sending. This communication between devices to regulate the data flow is called flow control. There are multiple stages of flow control in that one device tells the upstream device to go ahead and send, and the upstream device sends. The upstream device, in its turn, tells a further upstream device to go ahead and send. Typically between these devices, a flow control signal is needed so that each device knows when it is allowed to send. These devices, therefore, typically have queues 28 or FIFOs to store data packet temporarily. There may be an input queue and/or an output queue on each device. Some devices might not even have a queue but this is an image applied to most of cases.
Another example involves a personal computer or a workstation. A workstation or a server may have multiple CPUs. In any CPU, there might be queues to do certain work, to do web lookups, to do incremental statistics, etc. Again when one CPU is communicating to another, flow control is needed for passing work between the two CPUs.